package other._3;

import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author mazouri
 * @create 2022-01-03 11:47
 */
public class TSP {
    //right:1 left:-1
    private static final int LEFT = -1;
    private final int[][] graph;
    //保存每个路径对应的长度
    private LinkedList<Integer> dist;

    public TSP(int[][] graph) {
        this.graph = graph;
        this.dist = new LinkedList<>();
    }

    private static class PathCost{
        private String path;
        private Integer cost;

        public PathCost(String path, Integer cost) {
            this.path = path;
            this.cost = cost;
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 15, 6, 16, 4},
                {15, 0, 3, 10, 5},
                {6, 3, 0, 7, 9},
                {16, 10, 7, 0, 8},
                {4, 5, 9, 8, 0}
        };
        TSP t = new TSP(graph);
        LinkedList<int[]> list = t.permutations(4);
        LinkedList<PathCost> pathCosts = new LinkedList<>();
        for (int i = 0; i < list.size(); i++) {
            StringBuilder sb = new StringBuilder();
            int[] path = list.get(i);
            sb.append("0->");
            for (int k : path) {
                sb.append(k).append("->");
            }
            sb.append("0");
            pathCosts.add(new PathCost(sb.toString(),t.dist.get(i)));
        }
        pathCosts.sort(Comparator.comparingInt(o -> o.cost));
        System.out.println("路线                距离");
        for (PathCost pathCost : pathCosts) {
            System.out.println(pathCost.path+"    "+pathCost.cost);
        }
    }

    public LinkedList<int[]> permutations(int n) {
        LinkedList<int[]> permutations = new LinkedList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        int[] mobile = new int[n];
        for (int i = 0; i < n; i++) {
            first[i] = i + 1;
            mobile[i] = LEFT;
        }
        permutations.add(first);

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += graph[i][i + 1];
        }
        sum += graph[n][0];
        dist.add(sum);

        while (true) {
            int[] last = permutations.get(permutations.size() - 1).clone();
            int k = findLargestMobile(last, mobile);
            if (k == -1) break;
            int max = last[k];
            int side = mobile[k] == LEFT ? k - 1 : k + 1;
            computerDist(last,k,side);

            swap(last, k, side);
            swap(mobile, k, side);
            reverseLarger(last, mobile, max);
            permutations.add(last);
        }

        return permutations;
    }

    private void computerDist(int[] last, int k, int side) {
        int left = Math.min(k, side);
        int right = Math.max(k, side);
        int lleft = left - 1;
        int rright = right + 1;
        int l = last[left];
        int ll = lleft == -1 ? 0 : last[lleft];
        int r = last[right];
        int rr = rright == last.length ? 0 : last[rright];

        Integer pre = dist.getLast();
        pre = pre - graph[ll][l] - graph[r][rr] + graph[ll][r] + graph[l][rr];
        dist.add(pre);
    }


    /**
     * 元素指着比它小的元素，就是可移动的
     */
    private int findLargestMobile(int[] array, int[] mobile) {
        int k = -1;// -1 代表没有可移动元素了
        int max = -1;
        for (int i = 0; i < array.length; i++) {
            int j = mobile[i] == LEFT ? i - 1 : i + 1;
            if (j < 0 || j >= array.length) continue;
            if (array[i] > array[j] && array[i] > max) {
                max = array[i];
                k = i;
            }
        }
        return k;
    }

    private void reverseLarger(int[] array, int[] mobile, int max) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) mobile[i] = -mobile[i];
        }
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
